package list

// Problem Definition: https://leetcode.cn/problems/find-the-duplicate-number/

func FindDuplicate(nums []int) int {
	var slow, fast int
	slow, fast = nums[slow], nums[nums[fast]]
	for slow != fast {
		slow, fast = nums[slow], nums[nums[fast]]
	}

	slow = 0
	for slow != fast {
		slow, fast = nums[slow], nums[fast]
	}

	return slow
}
